'''
https:#leetcode.cn/problems/lfu-cache/
'''
from collections import defaultdict, deque

class Node:
    def __init__(self, k=-1, v=-1):
        self.freq = 0
        self.key = k
        self.value = v
        self.next = None
        self.prev = None
def default_list():
    head = Node()
    tail = Node()
    head.next = tail
    tail.prev = head
    return head, tail

# 双map
class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = float('inf')                # for delete
        self.freq_map = defaultdict(default_list)   # freq -> nodes
        self.key_map = {}                           # key -> node

    def _delete_from_freq(self, node):
        if not node.prev: return
        node.prev.next = node.next
        node.next.prev = node.prev
        # if node.prev == self.freq_map[node.freq][0] and node.next == self.freq_map[node.freq][1]:
        #     del self.freq_map[node.freq]

    def _increase(self, node):
        # 从原频率链表删除，并加入新的频率链表中
        self._delete_from_freq(node)
        node.freq += 1
        _, tail = self.freq_map[node.freq]
        prev = tail.prev
        node.prev = prev
        node.next = tail
        prev.next = node
        tail.prev = node
        # 更新最小频率，以方便超出容量后的删除
        self.min_freq = min(self.min_freq, node.freq)
        # if self.min_freq == node.freq - 1 and node.freq - 1 not in self.freq_map:
        #     self.min_freq = node.freq
        if self.min_freq == node.freq - 1:
            head, tail = self.freq_map[node.freq - 1]
            if head.next == tail:
                self.min_freq = node.freq

    def get(self, key: int) -> int:
        if key not in self.key_map: return -1
        res_node = self.key_map[key]
        self._increase(res_node)
        return res_node.value

    def put(self, key: int, value: int) -> None:
        if key in self.key_map:
            # update
            node = self.key_map[key]
            node.value = value
        else:
            # insert
            node = Node(key, value)
            self.key_map[key] = node
            self.size += 1
            if self.size > self.capacity:
                # delete
                del_node = self.freq_map[self.min_freq][0].next
                self._delete_from_freq(del_node)
                del self.key_map[del_node.key]
                self.size -= 1
        self._increase(node)


# 小根堆 实现 单次调用log(capacity)
class LFUCache2:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = {}
        self.pq = []
        self.timestamp = 0

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        i = self.dic[key]
        # heap
        freq, timestamp, key, v = self.pq[i]
        self.pq[i] = (freq + 1, self.timestamp, key, v)
        self.timestamp += 1
        self._heapify(i)
        return v

    def put(self, key: int, value: int) -> None:
        if key not in self.dic and len(self.pq) == self.capacity:
            _, _, k, _ = self.pq[0]
            self.dic[self.pq[-1][2]] = 0
            self.pq[0]= self.pq[-1]
            self.pq.pop()
            del self.dic[k]
            self._heapify(0)
        if key in self.dic:
            i = self.dic[key]
            freq, _, k, v = self.pq[i]
            self.pq[i] = (freq + 1, self.timestamp, k, value)
            self.timestamp += 1
            self._heapify(i)
        else:
            i = len(self.pq)
            self.dic[key] = i
            self.pq.append((1, self.timestamp, key, value))
            self.timestamp += 1
            self._heap_insert(i)

    def _heapify(self, i):
        pq = self.pq
        size = len(pq)
        while (l := (i << 1) + 1) < size:
            r = l + 1
            smallest = r if r < size and pq[r] <= pq[l] else l
            smallest = smallest if pq[smallest] <= pq[i] else i
            if i == smallest: break
            self.dic[pq[i][2]]          = smallest
            self.dic[pq[smallest][2]]   = i
            pq[i], pq[smallest] = pq[smallest], pq[i]
            i = smallest

    def _heap_insert(self, i):
        pq = self.pq
        while (parent := (i - 1) // 2) >= 0 and pq[i] < pq[parent]:
            self.dic[pq[i][2]]          = parent
            self.dic[pq[parent][2]]     = i
            pq[i], pq[parent] = pq[parent], pq[i]
            i = parent


# Your LFUCache object will be instantiated and called as such:
lfu=LFUCache(3)
lfu.put(2, 2)
lfu.put(1, 1)
print(lfu.get(2))
print(lfu.get(1))
print(lfu.get(2))
lfu.put(3, 3)
lfu.put(4, 4)
print(lfu.get(3))
print(lfu.get(2))
print(lfu.get(1))
print(lfu.get(4))

# lfu = LFUCache(2);
# lfu.put(1, 1);   # cache=[1,_], cnt(1)=1
# lfu.put(2, 2);   # cache=[2,1], cnt(2)=1, cnt(1)=1
# lfu.get(1);      # 返回 1
#                  # cache=[1,2], cnt(2)=1, cnt(1)=2
# lfu.put(3, 3);   # 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
#                  # cache=[3,1], cnt(3)=1, cnt(1)=2
# lfu.get(2);      # 返回 -1（未找到）
# lfu.get(3);      # 返回 3
#                  # cache=[3,1], cnt(3)=2, cnt(1)=2
# lfu.put(4, 4);   # 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
#                  # cache=[4,3], cnt(4)=1, cnt(3)=2
# lfu.get(1);      # 返回 -1（未找到）
# lfu.get(3);      # 返回 3
#                  # cache=[3,4], cnt(4)=1, cnt(3)=3
# lfu.get(4);      # 返回 4
#                  # cache=[3,4], cnt(4)=2, cnt(3)=3
